#pragma once

/////////////////////////////////////////
//二叉树类型定义

template <typename E>

struct  BiTNode
{
    E data;
    BiTNode *lchild,*rchild;
};

template<typename E>
using BiTree = BiTNode<E> *;

///////////////////////////////////////
//二叉树基本操作

//先序遍历二叉树 Preorder(T,visit)
template<typename E, typename F>
void Preorder(BiTree<E>T,F visit)
{
    if(T){
        visit(T->data);
        Preorder(T->lchild,visit);
        Preorder(T->rchild,visit);

    }
}

//中序遍历二叉树 Inorder（T,visit）
template<typename E, typename F>
void Inorder(BiTree<E>T,F visit)
{
    
    if(T){
        Inorder(T->lchild,visit);
        visit(T->data);
        Inorder(T->rchild,visit);

    }
}

//后序遍历二叉树 Posterder(T,visit)
template<typename E, typename F>
void Postorder(BiTree<E>T,F visit)
{
     
    if(T){
        Postorder(T->lchild,visit);
        Postorder(T->rchild,visit);
        visit(T->data);

    } 
}


///求二叉树结点数

template<typename E>
int NodeCount(BiTree<E> T)
{
    if(T == nullptr)
    return 0;
    auto L = NodeCount(T->lchild);
    auto R = NodeCount(T->rchild);
    return L + R +1;
}

///求二叉树叶子结点数

template<typename E>
int LeafCount(BiTree<E> T)
{
    if(T == nullptr)
    return 0;
    if(T->lchild == nullptr && T->rchild == nullptr)
    return 1;
    else
    {
    auto L = LeafCount(T->lchild);
    auto R = LeafCount(T->rchild);
    return L + R;    
    }
}


///求二叉树深度

template<typename E>
int Depth(BiTree<E> T)
{
    if (T == nullptr)
    return 0;
    else{
    auto L = Depth(T->lchild);
    auto R = Depth(T->rchild);
    return L >R ? L + 1 : R + 1;
    }
}
#include<iostream>
using std::cout;
using std::endl;

///打印二叉树
template <typename E>
void Print(BiTree<E> T, char prefix = '=', int level = 0)
{
    if (T) {
        Print(T->rchild,'/',level + 1);
        for (int i = 0; i < level; ++i) cout << "   ";
        cout << prefix << " " << T->data << endl;
        Print(T->lchild, '\\', level + 1);
    }
}

#include<iostream>
using std::cin;
using std::noskipws;

///建立二叉树 CreateBinarytree()
BiTree<char> CreateBinaryTree()
{
    char c;
    cin >> noskipws >> c;
    if (c == ' ') 
        return nullptr;
    else
    {
    auto T = new BiTNode<char>{c, nullptr,nullptr};
    T->lchild = CreateBinaryTree();
    T->rchild = CreateBinaryTree();
    return T;
    }
   
}

///销毁二叉树 Destroy(&T)
template<typename E>
void Destroy(BiTree<E> &T)
{
    if (T) {
        Destroy(T->lchild);
        Destroy(T->rchild);
        delete T;
        T = nullptr;
    }
}


/////////////////////////////////////
//二叉排序树基本操作

//二叉排序树查找算法 SearchBST(T,e)
template<typename E>
BiTree<E> SearchBST(BiTree<E> T, E e)
{
    if (!T || T->data == e)
        return T;
    else  if (e < T->data )
        return SearchBST(T->lchild,e);
    else
        return  SearchBST(T->rchild,e);

}

///二叉排列树找最小 FindMinBST(T)
template<typename E>
BiTree<E> FindMinBST(BiTree<E> T)
{
    if (T)
        while (T->lchild)
            T= T->lchild;
        return T;

}

///二叉排列树找最大 FindMaxBST（T)
template<typename E>
BiTree<E> FindMaxBST(BiTree<E> T)
{
    if (T)
        while (T->rchild)
            T = T->rchild;
    return T;
}


///二叉排列树插入 InsertBST（&T,e）
template<typename E>
void InsertBST(BiTree<E> &T, E e)
{
    if (T == nullptr)
        T = new BiTNode<E>{e, nullptr, nullptr};
    else if (e< T->data)
        InsertBST(T->lchild, e);
    else if (e> T->data)
        InsertBST(T->rchild, e);
    else;
}


///二叉排序树删除 DeleteBST(&T,e)
template<typename E>
void DeleteBST(BiTree<E> &T, E e)
{
    if (T == nullptr) return;
    else if (e < T->data)
        DeleteBST(T->lchild, e);
    else if (e > T->data)
        DeleteBST(T->rchild, e);
    else {// T->data == e
        if(T->lchild && T->rchild)
        {
            //T 有两个子树
            T->data = FindMaxBST(T->lchild)->data;
            DeleteBST(T->lchild,T->data);
        }
        else
        {
            //T 至多有一个子树
            auto oldNode = T;
            T= T->lchild ? T->lchild : T->rchild;
            delete oldNode;
        }

    }
}